/*

请设计实现一棵前缀树Trie，它有如下操作。

● 函数insert，在前缀树中添加一个字符串。

● 函数search，查找字符串。如果前缀树中包含该字符串，则返回true；否则返回false。

● 函数startWith，查找字符串前缀。如果前缀树中包含以该前缀开头的字符串，则返回true；否则返回false。

*/
#include <string>
#include <iostream>
using namespace std;
class TrieNode{
public:
    bool isWord;
    TrieNode * childern[26];
    TrieNode(){
        for(int i = 0; i < 26; i++)
            childern[i] = NULL;
        isWord = false;
    }
};
class Trie{
private:
    TrieNode *root;
public:
    Trie(){
        root = new TrieNode;
    }
    void insert(string s){
        TrieNode* node = root;
        for(char c : s){
            if(node->childern[c - 'a'] == NULL){
                node->childern[c - 'a'] = new TrieNode;
            }
            node = node->childern[c - 'a'];
        }
        node->isWord = true;
    }
    bool search(string s){
        TrieNode* node = root;
        for(char c : s){
            if(node->childern[c - 'a'] == NULL)
                return false;
            node = node->childern[c - 'a'];
        }
        return node->isWord;
    }
    bool startWith(string s){
        TrieNode* node = root;
        for(char c : s){
            if(node->childern[c - 'a'] == NULL)
                return false;
            node = node->childern[c - 'a'];
        }
        return true;
    }
};